In recent years, with the development of digital recording equipment and digital communication equipment, an important issue has been raised on how errors of digital data are reduced during the recording or reproduction, or transmission or reception of digital data. Thus, for correction of errors of digital data, error correcting codes are used in various types of equipments that treat digital data. The Reed-Solomon code is also one type of such error correcting codes, and is used primarily in, for example, digital recording devices such as PD drive units utilizing phase change.
The Reed-Solomon code is a multi-element cyclic Hamming code in which the code word consists of elements of a Galois field GF(2.sup.N) whose number of elements is 2.sup.N, and in which if .alpha. is the primitive element of GF(2.sup.N), then the generator polynomial can be expressed by the following equation: EQU G(X)=(X-.alpha..sup.0)(X-.alpha..sup.1) . . . (X-.alpha..sup.d-2)(1)
Hereinafter, computational operations including the Equation (1) will be all executed on the Galois field GF(2.sup.N). Also, d denotes the minimum inter-code distance.
Code words in the Reed-Solomon code are generated as follows:
If an information word vector I is expressed as follows: EQU I=(i.sub.0, i.sub.1. . . , i.sub.k-1) , (2)
then the information polynomial I(X) can be expressed as follows: EQU I(X)=i.sub.0 .multidot.X.sup.k-1 +i.sub.1 .multidot.X.sup.k-2 +. . . +i .sub.k-2 .multidot.X+i.sub.k-1 ( 3)
where i.sub.0, i.sub.1, . . . and i.sub.k-1 are information symbols, respectively, and are associated with vector representations of elements on the Galois field GF(2.sup.N) by handling N bits as one set with respect to bit data that are the source of information. PA1 where the code word vector A represented by the Equation (10) contains the information word vector I as it is, proving that it is a systematic code. In this case, the code word vector A is a (n, k) systematic code. Upon creating a code word, a vector R to be added to the information word vector, that is, EQU R=(r.sub.0, r.sub.1, . . . , r.sub.n-k-1) (11) PA1 (a) 8-bit EXCLUSIVE-OR computing units 195 to 206; PA1 (b) coefficient multipliers 171 to 182 having coefficients k.sub.12 to k.sub.1 on the Galois field; PA1 (c) 8-bit latches 183 to 194; and PA1 (d) an initial-value setting circuit 207 for clearing to 0 the contents of the 8-bit latches 183 to 194 upon a reset. PA1 product data storage device for previously storing a plurality of product data on the Galois field between each of the input data and each of coefficients of a generator polynomial of the Reed-Solomon code, with handling a plurality of b product data as one set for each address, after previously computing the plurality of product data; PA1 first storage device comprising a natural number of m storage units each having a storage capacity of N.times.b bits; PA1 read control device for controlling said product data storage device to read out the plurality of product data stored in said product data storage device in parallel by handling a plurality of b product data as one set, in response to the input data; PA1 exclusive OR operation device having first and second input terminals each of N.times.b bits, the plurality of b product data read out in parallel from the product data storage device by said read control device being inputted to the first input terminal, the exclusive OR operation device computing exclusive OR data between data inputted to the first input terminal and data inputted to the second input terminal, and outputting resulting computation data; PA1 first selecting device for controlling the first storage device to selectively and sequentially read out and output data stored in the m storage units every one storage unit thereof, to output data of more significant N.times.(b-1) bits out of the selectively read out and outputted data of N.times.b bits, to less significant N.times.(b-1) bits of the second input terminal of the exclusive OR operation device, and to write the resulting computation data outputted from the exclusive OR operation device into one of the m storage units by selectively and sequentially switching the m storage units; and PA1 second storage device having a storage capacity of N bits, for temporarily storing data of the less significant N bits out of the N.times.b bit data selectively outputted from one of the m storage units by the first selecting device, and for outputting temporarily stored data to the more significant N bits of the second input terminal of the exclusive OR operation device, PA1 wherein when sequentially inputting the input data into the product data storage device, the m storage unit of the first storage device generates parity data, PA1 wherein the device further comprises: PA1 received word storage device for storing an input received word comprised of a plurality of received symbols including input data and parity data associated with the input data, in a unit of the received symbols; PA1 remainder computing device comprising the device for error correcting coding as claimed in Claim 1, the remainder computing device computing and outputting a remainder for the input received word by using a generator polynomial of the Reed Solomon code; PA1 error numerical value and error position computing device for computing and outputting a set of an error position in the received word and an error numerical value corresponding to the error position, based on the remainder outputted from the remainder computing device; PA1 control device for reading out from said received word storage device and outputting a received symbol in the error position stored in the received word storage device based on the error position in the received word outputted from the error numerical value and error position computing device; PA1 exclusive OR operation device for computing exclusive OR data between the received symbol in the error position outputted from the read control device and the error numerical value corresponding to the error position outputted from the error numerical value and error position computing device, and outputting resulting computation data; and PA1 write control device for writing the resulting computation data outputted from the exclusive OR operation device into the error position in the received word storage device, and for correcting the received symbol in the error position. PA1 previously storing in a product data storage device a plurality of product data on the Galois field between each of the input data and each of coefficients of a generator polynomial of the Reed-Solomon code, with handling a plurality of b product data as one set for each address, after previously computing the plurality of product data; PA1 controlling the product data storage device to read out the plurality of product data stored in the product data storage device in parallel by handling a plurality of b product data as one set, in response to the input data; PA1 by using exclusive OR operation device having first and second input terminals each of N.times.b bits, the plurality of b product data read out in parallel from the product data storage device by the read control device being inputted to the first input terminal, computing exclusive OR data between data inputted to the first input terminal and data inputted to the second input terminal, and outputting resulting computation data; PA1 controlling the first storage device comprising m storage unit each having a storage capacity of N.times.b bits, to selectively and sequentially read out and output data stored in said m storage units every one storage unit thereof, to output data of more significant N.times.(b-1) bits out of the selectively read out and outputted data of N.times.b bits, to less significant N.times.(b-1) bits of the second input terminal of the exclusive OR operation device, and to write the resulting computation data outputted from said exclusive OR operation device into one of the m storage units by selectively and sequentially switching the m storage units; PA1 by using second storage device having a storage capacity of N bits, temporarily storing data of the less significant N bits out of the N.times.b bit data selectively outputted from one of the m storage units, and outputting temporarily stored data to the more significant N bits of the second input terminal of the exclusive OR operation device; PA1 when sequentially inputting the input data into the product data storage device, generating parity data in the m storage unit of said first storage device; and PA1 sequentially outputting the respective parity data generated by the m storage units by selectively and sequentially switching the m storage units every one storage unit in succession to the input data. PA1 storing in a received word storage device an input received word comprised of a plurality of received symbols including input data and parity data associated with the input data, in a unit of the received symbols; PA1 by the method for error correcting coding as claimed in Claim 4, computing and outputting a remainder for the input received word by using a generator polynomial of the Reed Solomon code; PA1 computing and outputting a set of an error position in the received word and an error numerical value corresponding to the error position, based on the outputted remainder; PA1 reading out from the received word storage device and outputting a received symbol in the error position stored in the received word storage device based on the error position in the outputted received word; PA1 computing exclusive OR data between the received symbol in the outputted error position and the error numerical value corresponding to the outputted error position, and outputting resulting computation data; and PA1 writing the outputted resulting computation data into the error position in the received word storage device, and correcting the received symbol in the error position.
Then, a code polynomial A(X) can be calculated from the information polynomial I(X) and the generator polynomial G(X) by using the following equation: EQU A(X)=I(X).multidot.G(X) (4)
However, the code obtained would not be a systematic code. Therefore, a code word is created as follows.
First of all, the information polynomial I(X) is multiplied by X.sup.n-k, and the result is divided by G(X). If the quotient is Q(X) and the remainder is R(X), then the following expression can be given: EQU I(X).multidot.X.sup.n-k =Q(X).multidot.G(X)+R(X) (5)
Then, if EQU A(X)=R(X)+I(X).multidot.X.sup.n-k ( 6)
then the following equation can be obtained from the Equation (5): EQU A(X)=Q(X).multidot.G(X) (7)
The A(X) calculated by the Equation (7) is divisible by the generator polynomial G(X), thus resulting in a code polynomial. If the code polynomial R(X) is expressed as follows: EQU R(X)=r.sub.0 .multidot.X.sup.n-k-1 +r.sub.1 .multidot.X.sup.n-k-2 +. . . +r.sub.n-k-2 .multidot.X+r.sub.n-k-1 ( 8)
then the code polynomial A(X) expressed by the Equation (6) can be expressed as follows: ##EQU1##
The code word represented by the code polynomial of the Equation (9) can be represented in vector representation as follows: EQU A=(i.sub.0, i.sub.1, . . . , i.sub.k-1, i r.sub.0, r.sub.1, . . . , r.sub.n-k-1) (10)
is a parity vector.
The code generated in this way as shown above is written as a Reed-Solomon code RS (n, k, d=n-k+1).
FIG. 12 shows an example of the device for error correcting coding according to the prior art using the Reed-Solomon code. This circuit performs the division of polynomials having coefficients of Galois field GF(2.sup.N) Referring to FIG. 12, the device for error correcting coding comprises:
In this device for error correcting coding, input data is inputted to a first input terminal of the EXCLUSIVE-OR computing unit 206. The output data from the output terminal of the EXCLUSIVE-OR computing unit 206 is inputted to the 8-bit latch 183 via the coefficient multiplier 171, while the output data therefrom is inputted to the EXCLUSIVE-OR computing units 195 to 205 via the coefficient multipliers 172 to 182, respectively. Further, the 8-bit latches 183 to 194 and the EXCLUSIVE-OR computing units 195 to 206 are arranged alternately and connected in series so that data is transferred from the latch 183 toward the latch 194.
Next, a case where a Reed-Solomon code RS (32, 20, d=13) with 8 bits taken as 1 symbol is actually encoded by using the device for error correcting coding of FIG. 12.
It is noted that the primitive polynomial m(X), the primitive element .alpha. and the generator polynomial G(X) are defined as follows: EQU m(X)=X.sup.8 +X.sup.4 +X.sup.3 +X.sup.2 +1 (12) EQU .alpha.(00000010) (13) ##EQU2##
In addition, k.sub.1 to k.sub.12 in the Equation (14) represent coefficients to be multiplied to X.sup.11 to X.sup.0, as a result of developing the generator polynomial G(X) and arraying the terms in the descending order of X.
When a first information symbol i.sub.000, which is first input data, is inputted to the EXCLUSIVE-OR computing unit 206, an EXCLUSIVE-OR of the first information symbol i.sub.000 and 00H, which is the output data from the 8-bit latch 194, is computed, and then, data of the computation result is inputted to the Galois field coefficient multipliers 171 to 182. It is noted that "H" in 00H denotes a hexadecimal representation, which is the case also hereinafter. In this case, if the data inputted to the Galois field coefficient multipliers 171 to 182 is d.sub.000, then the data d.sub.000, which is the EXCLUSIVE-OR of the first information symbol i.sub.000 and the data of 00H can be expressed by the following equation: EQU d.sub.000 =i.sub.000 (15)
This corresponds to a computation which presents in column number R1 and over three rows of step S101 of FIG. 13. Next, the Galois field coefficient multipliers 171 to 182 output products on the Galois field of the input data d.sub.000 and their respective coefficients k.sub.12 to 1. These products correspond to the data which present in column numbers R13 to R2 and on the second row of step S101 of FIG. 13.
Next, the output data from the Galois field coefficient multipliers 171 to 182 are stored in the 8-bit latches 183 to 194, respectively. Now the data stored in the respective latches 183 to 194 are referred to as p.sub.000 to p.sub.011, respectively, these data values correspond to results of performing computations which present in column numbers R13 to R2 and over the three rows of step S101 of FIG. 13, respectively. In addition, the addition sign in FIG. 13 represents an EXCLUSIVE-OR operation, and hereinafter an operation EOR represents an EXCLUSIVE-OR operation.
Next, when a second information symbol i.sub.001, which is second input data, is inputted to the EOR computing unit 206, an EOR of the second information symbol i.sub.000 and p.sub.011, which is output data from the 8-bit latch 194, is computed, and then, data of the computation result is inputted to the Galois field coefficient multipliers 171 to 182. In this case, if the data inputted to the Galois field coefficient multipliers 171 to 182 is d.sub.001, then the data d.sub.001, which is the EOR of the second information symbol i.sub.001 and the data p.sub.011 can be expressed by the following equation: EQU d.sub.001 .sub.001 +p.sub.001 ( 16)
This corresponds to a computation which presents in column number R2 and over three rows of step S101 of FIG. 13. Next, the Galois field coefficient multipliers 171 to 182 output products on the Galois field of the input data d.sub.001 and their respective coefficients k.sub.12 to .sub.1. These products correspond to the data which presents in column numbers R14 to R3 and on the second row of step S102 of FIG. 13.
Next, the output data from the Galois field coefficient multipliers 171 to 182 are stored in the 8-bit latches 183 to 194, respectively. Now the data stored in the latches 183 to 194 are referred to as p.sub.012 to p.sub.023, respectively, these data values correspond to results of performing computations which present in column numbers R14 to R3 and over the three rows of step S102 of FIG. 13, respectively.
Likewise also for the following, as the information symbol i.sub.002 through information symbol i.sub.019 are inputted to the EOR computing unit 206, computations as shown in FIG. 13 are continued, and finally, parity words (p.sub.228, p.sub.229, . . . , p.sub.229) which are remainders of dividing the information words (i.sub.000, i.sub.001, . . . , i.sub.019) by the generator polynomial (the Equation (14)), are stored in the 8-bit latches 183 to 194, respectively. Adding the finally obtained parity symbols p.sub.228, p.sub.229, . . . , and p.sub.239 in succession to the information symbols i.sub.000, i.sub.001, . . . , and i.sub.019 that have already been inputted completes a code word (i.sub.000, i.sub.001, . . . , i.sub.019, p.sub.228, p.sub.229, . . . , p.sub.239).
However, in the device for error correcting coding as shown in FIG. 12, because the Galois field coefficient multipliers 171 to 182 have complex circuits, respectively, a large-scale circuit would be involved in encoding symbols of a long minimum inter-code distance. Also, for the device for error correcting coding as shown in FIG. 12, it would be difficult to change the minimum inter-code distance without changing the arrangement of the device. In order to change the minimum inter-code distance without changing the arrangement of the device, it is necessary to make the coefficients of the Galois field coefficient multipliers changeable without changing the arrangement of the device and to provide a circuit configuration that allows the loop of division circuits to be changed without changing the arrangement of the device. The implementation of these needs would result in further complex circuits.
A first object of the present invention is to provide a device and method for error correcting coding which solves the above-mentioned problems, and which can be implemented with small-scale circuitry, as compared with that of the prior art, while fulfilling a practicable coding rate, and further which allows the minimum inter-code distance d to be freely changed without changing the arrangement of the device.
A second object of the present invention is to provide a device and method for error correcting decoding which can be implemented with small-scale circuitry, as compared with the prior art, while fulfilling a practicable decoding rate, and further which allows the minimum intercode distance d to be freely changed without changing the arrangement of the device.